// 给定一个二叉树

// struct TreeLinkNode {
//   TreeLinkNode *left;
//   TreeLinkNode *right;
//   TreeLinkNode *next;
// }
// 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

// 初始状态下，所有 next 指针都被设置为 NULL。

// 说明:

// 你只能使用额外常数空间。
// 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
// 示例:

// 给定二叉树，

//      1
//    /  \
//   2    3
//  / \    \
// 4   5    7
// 调用你的函数后，该二叉树变为：

//      1 -> NULL
//    /  \
//   2 -> 3 -> NULL
//  / \    \
// 4-> 5 -> 7 -> NULL

struct TreeLinkNode {
    int val;
    TreeLinkNode *left, *right, *next;
    TreeLinkNode(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
};

// 递归，由于子树有可能残缺，故需要平行扫描父节点同层的节点，找到他们的左右子节点。
class Solution1 {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *node = root->next;
        while (node) { // node是父节点同一层节点的孩子
            if (node->left) {
                node = node->left;
                break;
            }
            if (node->right) {
                node = node->right;
                break;
            }
            node = node->next;
        }
        if (root->right) root->right->next = node;
        if (root->left) root->left->next = root->right ? root->right : node;
        connect(root->right); // 先连接右孩子，不然左边可能连接不到右孩子
        connect(root->left);
    }
};

// 常数空间的解
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *dummy = new TreeLinkNode(0);
        TreeLinkNode *cur = dummy; // 每层的首结点的前一个结点
        TreeLinkNode *pre = root; // pre表示上一层的节点
        while (pre) {
            if (pre->left) {
                cur->next = pre->left;
                cur = cur->next;
            }
            if (pre->right) {
                cur->next = pre->right;
                cur = cur->next;
            }
            pre = pre->next;
            if (!pre) { // root为空，表示这一层已经遍历完毕
                cur = dummy; // 当前指针回到虚假头节点dummy
                pre = dummy->next; // 上一层的节点回到下一层第一个
                dummy->next = nullptr; // 虚假头节点清空，也就表示下移了一层
            }
        }
    }
};

#include "stdc++.h"

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

/* 层次遍历
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        queue<Node*> q{};
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            Node* pre{nullptr};
            for (int i{1}; i <= n; ++i) {
                Node* temp = q.front();
                q.pop();
                if (temp->left != nullptr) {
                    q.push(temp->left);
                }
                if (temp->right != nullptr) {
                    q.push(temp->right);
                }
                if (i != 1) {
                    pre->next = temp;
                }
                pre = temp;
            }
        }
        return root;
    }
};

/* 使用已建立的next指针
上一层建立好next链表之后，下一层可以通过上一层的链表来寻找next
时间复杂度：O(n)
空间复杂度：O(1)
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* start{root};
        while (start) {
            Node* pre{nullptr}; // 下一层的前一个节点
            Node* nextStart{nullptr}; // 下一层的头节点
            for (Node* p{start}; p != nullptr; p = p->next) { // 遍历上一层的链表
                if (p->left) {  
                    handle(pre, p->left, nextStart);
                }
                if (p->right) {
                    handle(pre, p->right, nextStart);
                }
            }
            start = nextStart;
        }
        return root;
    }
    void handle(Node* &pre, Node* &cur, Node* &nextStart) {
        if (pre != nullptr) {
            pre->next = cur;
        }
        if (nextStart == nullptr) {
            nextStart = cur;
        }
        pre = cur;
    }
};